﻿using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;

namespace WMM.Tapioca.Utilities
{
    public class Edge
    {
        public Vertex destination; // The destination Vertex of the Edge
        public Vertex source; // The destination Vertex of the Edge

        public Edge(Vertex s, Vertex d)
        {
            source = s;
            destination = d;
        }
    }

    public class Vertex
    {
        public String name;
        public LinkedList<Edge> outEdges; // The out-bound Edges of this Vertex
        public LinkedList<Edge> inEdges; // The in-bound Edges of this Vertex
        public int inDegree; // A convenient *scratch variable* for our algorithm to use
        public int degree; // A convenient *scratch variable* for our algorithm to use

        public Vertex(String nm)
        {
            name = nm;
            outEdges = new LinkedList<Edge>();
            inEdges = new LinkedList<Edge>();
            inDegree = 0;
            degree = 0;
        }
    }


    public class Graph
    {
        List<Vertex> vertexCollect;

        public List<Vertex> VertexCollect
        {
            get { return vertexCollect; }
            set { vertexCollect = value; }
        }

        public Graph()
        {
            vertexCollect = new List<Vertex>();
        }

        public List<Vertex> vertices()
        {
            return vertexCollect; // Return all Vertices in the Graph
        }

        public void addVertex(Vertex v)
        {
            vertexCollect.Add(v);
        }

        public void addEdge(String From, String To)
        {
            Edge e = null;

            foreach (Vertex v in vertexCollect)
            {
                if (v.name.Equals(From))
                {
                    foreach (Vertex vDest in vertexCollect)
                    {
                        if (vDest.name.Equals(To))
                        {
                            e = new Edge(v, vDest);
                            vDest.inEdges.AddLast(e);
                        }
                    }
                   
                    v.outEdges.AddLast(e);           
                }
            }
        }

        /// <summary>
        /// Return the list of neighbors of vertex v as in Iterable. </summary>
        /// <exception cref="java.lang.IndexOutOfBoundsException"> unless 0 <= v < V </exception>
        public virtual List<Vertex> adj(Vertex v)
        {
            List<Vertex> neighbors = new List<Vertex>();

            foreach (Edge e in v.outEdges)
            {
                neighbors.Add(e.destination);
            }
            foreach (Edge e in v.inEdges)
            {
                neighbors.Add(e.source);
            }

            return neighbors;
        }


        public long size()
        {
            // Return the number of Vertices in the Graph
            return vertexCollect.Count;
        }


        public void DependencyResolve(Vertex currentVertex, ref List<Vertex> resolved, ref List<Vertex> unresolved)
        {
            unresolved.Add(currentVertex);

            foreach (Edge edge in currentVertex.outEdges)
            {
                if (!resolved.Contains(edge.destination))
                {
                    if (unresolved.Contains(edge.destination))
                    {
                        throw new XbrlException("Circular reference detected: " + currentVertex.name + " --> " + edge.destination.name);
                    }
                    else
                    {
                        DependencyResolve(edge.destination, ref resolved, ref unresolved);
                    }
                }
            }

            resolved.Add(currentVertex);
            unresolved.Remove(currentVertex);
        }


        public Queue<Vertex> GetVerticesInDegreeZero()
        {
            Queue<Vertex> q; // Queue will store vertices that have in-degree of zero
            //long counter = 0;

            // Calculate the in-degree of all vertices and store on the Locator 
            foreach (Vertex vertex in this.vertices())
            {
                vertex.inDegree = 0;
            }

            foreach (Vertex vertex in this.vertices())
            {
                foreach (Edge edge in vertex.outEdges)
                {
                    Vertex destination = edge.destination;

                    if (destination != null)
                    {
                        destination.inDegree++;
                    }
                }
            }

            // Find all vertices with in-degree == 0 and put in queue 
            q = new Queue<Vertex>();

            foreach (Vertex vertex in this.vertices())
            {
                if (vertex.inDegree == 0)
                    q.Enqueue(vertex);
            }

            return q;
        }


    }

}
